#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result;
        if(root==NULL){
            return result;
        }
        vector<int> path;
        DFS(root,path,0,sum,result);
        return result;
    }
    void DFS(TreeNode* root,vector<int> path,int pathSum,int sum,vector<vector<int>>& result){
        if(root==NULL){
            return;
        }
        if(root->left==NULL&&root->right==NULL){
            if(pathSum+root->val==sum){
                path.push_back(root->val);
                result.push_back(path);
            }
            return;
        }
      
        path.push_back(root->val);
        pathSum += root->val;
        DFS(root->left,path,pathSum,sum,result);
        DFS(root->right,path,pathSum,sum,result);
    }  
};

